Crible d'Ératosthène - Corrigé

Énoncé

Soit  \(n\) un entier naturel supérieur ou égal à \(2\) .

Le crible d'Ératosthène est une méthode pour déterminer tous les nombres premiers inférieurs ou égaux à  \(n\) en procédant par élimination de la manière suivante :

• on fait la liste des entiers de  \(2\) à  \(100\) ;
• on prend le premier terme de la liste : \(2\) ; il est premier, donc on le conserve et on élimine tous ses multiples ;
• on recommence en prenant le premier terme de la liste restante, et ainsi de suite ;
• on s'arrête lorsque toute la liste a été parcourue (les nombres ont tous été soit sélectionnés en tant que nombres premiers, soit éliminés).

Utiliser cette méthode pour déterminer tous les nombres premiers inférieurs à \(100\) .

\(\begin{align*}\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline&2&3&4&5&6&7&8&9&10\\ \hline11&12&13&14&15&16&17&18&19&20\\ \hline21&22&23&24&25&26&27&28&29&30\\ \hline31&32&33&34&35&36&37&38&39&40\\ \hline41&42&43&44&45&46&47&48&49&50\\ \hline51&52&53&54&55&56&57&58&59&60\\ \hline61&62&63&64&65&66&67&68&69&70\\ \hline71&72&73&74&75&76&77&78&79&80\\ \hline81&82&83&84&85&86&87&88&89&90\\ \hline91&92&93&94&95&96&97&98&99&100\\ \hline\end{array}\end{align*}\)

Solution

Après avoir appliqué la méthode du crible d'Ératosthène, on obtient la liste des nombres premiers inférieurs à  \(100\) .

En les listant ligne par ligne à partir du tableau de départ, il reste :

• \(2\)  ;  \(3\)  ;  \(5\)  ;  \(7\)  ;
• \(11\)  ;  \(13\)  ;  \(17\)  ;  \(19\)  ;
• \(23\)  ;  \(29\)  ;
  
• \(31\)  ;  \(37\)  ;
  
• \(41\)  ;  \(43\)  ;  \(47\)  ;
  
• \(53\)  ;  \(59\)  ;
  
• \(61\)  ;  \(67\)  ;
  
• \(71\)  ;  \(73\)  ;  \(79\)  ;
  
• \(83\)  ;  \(89\)  ;
  
• \(97\) .